Міністерство освіти і науки України
Тернопільський національний технічний університет
імені Івана Пулюя
Кафедра комп’ютерних наук
ЛАБОРАТОРНА РОБОТА №2
з дисципліни “Теорія алгоритмів”
Тема роботи: Структури алгоритмів.
Тернопіль – 2010
Лабораторна робота №2
Тема роботи: Структури алгоритмів.
Мета роботи: Вивчення основних елементів структури обчислювальних алгоритмів.
Теоретичні відомості
Часто в інженерній практиці виникає необхідність порівняння технічних об(єктів. У цих випадках опис технічного об(єкта необхідно звести до таких математичних об(єктів як числа, вектори, матриці або функції. У цьому випадку порівнюютбся вже не самі об`єкти, а іх математичні представлення.
У таких випадках характерисртикою об(єктів є поняття норми, а самі об(єкти розглядають у відповідних метричних просторах, наприклад . Нормою в називається дійснозначна функція (позначають -норма Х), яка задовільняє такі умови:
для будь-якого , причому тільки якщо ;
для кожного і ;
для кожного ;
Найбільш поширені слідуючі норми:
для дійсних чисел: модуль числа ;
для комплексних чисел:
модуль комплексного числа
для векторів :
- норма (норма Чебишева) ;
- норма (Евклідова норма) ;
- норма ;
для матриць:
норма Фробеніуса ;
l1- норма ,
де - j-ий стовбець матриці X
для функцій:
, де T – интервал задання функції X(t).
Порівняння норм здійснюється так само як порівняння дійсних чисел.
В деяких випадках виникає необхідність
391
299
Знаходження спільної міри кількох об`єктів. У
299
1
цьому випадку поріввнюються значення
299
92
норми, а для знаходження найбільшого
276
3
спільного дільника (НСД) використовується
92
23
алгоритм Евкліда. Приклад знаходження НСД
92
4
за алгоритмом Евкліда представлено на рис.1. У цьому прикладі шукають НСД чисел
0
391 і 299. Значення НСД буде рівне останньому дільнику, після ділення на який остача рівна 0, тобто НСД рівне 23.
Рис.1
Для знаходження НСД трьох і більше чисел спочатку знаходять НСД будь-яких двох чисел а потім – знайденого НСД і одного з чисел що залишилися.
Завдання до лабораторної роботи.
Згідно заданого варіанту завдань написати програму на мові ПАСКАЛЬ або С++ і реалізувати її на ЕОМ.
Представити результати роботи програми.
Оформити звіт по виконаній роботі.
7
Знайти спільну міру відстані між точками А1(345,921), А2(7209,2923) i B1(-987,352), B2(2685,1423).
Текст програми
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ExtCtrls;
type
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
Button4: TButton;
Edit1: TEdit;
Label1: TLabel;
procedure Button1Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
i,k:real;
x,y:integer;
kil:integer;
L:array [1..2,1..4] of real;
d:array [1..2,1..4] of real;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
begin
form1.Memo1.Visible:=true;
form1.Button4.Enabled:=true;
form1.Memo1.Lines.text:='ÌÀÑÈÂ I:';
begin
L[1,1]:=345;
L[1,2]:=921;
L[1,3]:=7209;
L[1,4]:=2923;
d[2,1]:=-987;
d[2,2]:=352;
d[2,3]:=2685;
d[2,4]:=1423;
k:=sqrt((L[1,1]*L[1,1])+(L[1,2]*L[1,2])+(L[1,3]*L[1,3])+(L[1,4]*L[1,4]));
i:=sqrt((d[2,1]*d[2,1])+(d[2,2]*d[2,2])+(d[2,3]*d[2,3])+(d[2,4]*d[2,4]));
y:=round(k);
x:=round(i);
form1.Memo1.Lines.Add('1: ' +floattostr(L[1,1]));
form1.Memo1.Lines.Add('2: ' +floattostr(L[1,2]));
form1.Memo1.Lines.Add('3: ' +floattostr(L[1,3]));
form1.Memo1.Lines.Add('4: ' +floattostr(L[1,4]));
form1.Memo1.Lines.Add(' ');
form1.Memo1.Lines.Add('Åâêë³äîâà íîðìà: ' +floattostr(y));
form1.Memo1.Lines.Add(' ');
form1.Memo1.Lines.Add(' ');
form1.Memo1.Lines.add('ÌÀÑ...
